package com.wxg.algorithm.chapter07;

import java.util.ArrayList;
import java.util.List;

/**
 * date : 2018年08月14日
 *
 * 稠密图 - 邻接矩阵
 *
 */
public class DenseGraph {

    private int n;
    private int m;
    private boolean directed;
    private boolean[][] g;

    public DenseGraph( int n, boolean directed ){
        this.n = n;
        this.m = 0;
        this.directed = directed;
        g = new boolean[n][n];
    }

    public int V(){
        return n;
    }

    public int E(){
        return m;
    }

    public void addEdge( int v, int w ){

        if ( hasEdge( v, w ) ){
            return;
        }

        if ( v >= 0 && v < n && w >= 0 && w < n ){
            g[v][w] = true;
            if ( !directed ){
                g[w][v] = true;
            }

            m++;
        }
    }

    public boolean hasEdge( int v, int w ){
        if ( v >= 0 && v < n && w >=0 && w < n ){
            return g[v][w];
        }

        throw new RuntimeException("参数错误");
    }

    /**
     * 返回图中一个顶点的所有邻边
     * 由于java使用引用机制, 返回一个 List 不会带来额外开销。(相对于C++)
     *
     * java.lang.Iterable : http://tool.oschina.net/uploads/apidocs/jdk-zh/java/lang/Iterable.html
     *
     * @param v
     * @return
     */
    public Iterable<Integer> adj( int v ) {
        if ( v >= 0 && v < n ){
            List<Integer> adjList = new ArrayList<>();
            for ( int i = 0; i < n; i ++ ){
                if ( g[v][i] ){
                    adjList.add(i);
                }
            }
            return adjList;
        }

        throw new RuntimeException("参数错误");
    }
}
